package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/4/15
 * @description <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode34_在排序数组中查找元素的第一个和最后一个位置 {
    /**
     * 利用二分搜索法
     * 首先找到数组中第一个等于target元素的下标,记为left
     * 然后找到数组中第一个大于target元素的下标-1,记为right
     * 最后判断left和right是否均合法,如果合法就返回left和right
     * <p>
     * 时间复杂度O(logN) 进行两次二分搜索
     * 空间复杂度O(1)
     */
    public int[] searchRange(int[] nums, int target) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return new int[]{-1, -1};
        }

        //首先找到数组中第一个等于target元素的下标,记为left
        int left = binarySearchFirstGreater(nums, target, true);

        //然后找到数组中第一个大于target元素的下标-1,记为right
        int right = binarySearchFirstGreater(nums, target, false) - 1;

        //最后判断left和right是否均合法,如果合法就返回left和right
        if (left <= right && right < nums.length && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }

        //不存在
        return new int[]{-1, -1};


    }

    /**
     * 在数组nums中进行二分查找,找到第一个大于target元素的下标
     * 如果eq=true,则找到第一个大于等于target元素的下标
     */
    private int binarySearchFirstGreater(int[] nums, int target, boolean eq) {
        int l = 0;
        int r = nums.length - 1;
        int result = nums.length;

        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if ((eq && nums[mid] >= target) || nums[mid] > target) {
                result = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return result;
    }
}
